package org.example.struct.array;

/**
 * @author liyishan
 * @date 2024/1/9 09:07
 * @apiNote
 */

public class Test00014LongestCommonPrefix {
    public static void main(String[] args) {
        String[] strs = {"flower","flow","flight"};
        System.out.println(longestCommonPrefix(strs));
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }

    public static String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int lenth = strs[0].length();
        int count = strs.length;
        for(int i = 0; i < lenth; i++){
            char c = strs[0].charAt(i);
            for(int j = 1; j < count; j++){
                if(i == strs[j].length() || strs[j].charAt(i) != c){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }


    public static String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }else{
            return longestCommonPrefix(strs,0,strs.length-1);
        }
    }

    public static String longestCommonPrefix(String[] strs,int start,int end){
        if(start == end){
            return strs[start];
        }else{
            int mid = (start + end)/2;
            String lcpLeft = longestCommonPrefix(strs,start,mid);
            String lcpRight = longestCommonPrefix(strs,mid+1,end);
            return commonPrefix(lcpLeft,lcpRight);
        }
    }

    public static String commonPrefix(String lcpLeft,String lcpRight){
        int minLength = Math.min(lcpLeft.length(),lcpRight.length());
        for(int i = 0;i < minLength;i++){
            if(lcpLeft.charAt(i) != lcpRight.charAt(i)){
                return lcpLeft.substring(0,i);
            }
        }
        return lcpLeft.substring(0,minLength);
    }
}
